from collections import OrderedDict

""" Redis 底层就是LRU算法
https://www.cnblogs.com/leeyong49/p/16598519.html

问题描述：
    首先考虑这样的一个业务场景,小王在A公司上班，有一天产品提出了一个需求：
        “咱们系统的用户啊，每天活跃的就那么多，有太多的僵尸用户，根本不登录，你能不能考虑做一个筛选机制把这些用户刨出去，并且给活跃的用户做一个排名，
        我们可以设计出一些奖励活动，提升咱们的用户粘性，咱们只需要关注那些活跃的用户就行了“。
    小王连忙点头，说可以啊，然而心里犯起嘀咕来了：
        这简单，按照常规思路，给用户添加一个最近活跃时间长度和登录次数，然后按照这两个数据计算他们的活跃度，最后直接排序就行了。嘿嘿，简直完美!
    不过！
        用户表字段已经很多了，又要加两个字段，然后还得遍历所有的数据排序？
        这样查询效率是不是会受影响啊？
        并且公司的服务器上次就蹦过一次，差点没忙出命来才调好。
        有没有更优雅的一种方式呢？
    小王面朝天空45°，陷入了无限的思考中.....
    
    
LRU是什么？
    按照英文的直接原义就是Least Recently Used --> 最近最久未使用法，也就是最近最少使用的意思
    是一种内存管理算法，该算法最早应用于Linux操作系统。
    
    它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
    
    基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！
    
    它的主要衡量指标是使用的时间，附加指标是使用的次数。
    
    在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！
    因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。

当小王看到LRU的时候，瞬间感觉抓住了救命稻草，这个算法不是就完全契合产品的需求吗？
只要把用户数据按照LRU去筛选，利用数据结构完成的事情，
完全减少了自己存储、添加字段判断、排序的过程，这样对于提高服务器性能肯定有很大的帮助，岂不美哉！
"""
"""在LRU算法中，使用了一种有趣的数据结构，这种数据结构叫作哈希链表。


什么是哈希链表呢？

    我们都知道，哈希表是由若干个 Key-Value 组成的。在“逻辑”上，这些 Key-Value 是无所谓排列顺序的，谁先谁后都一样。
    
    在哈希链表中，这些 Key-Value 不再是彼此无关的了，而是被一个链条串了起来。
    每一个 Key-Value 都具有它的前驱 Key-Value、后继 Key-Value，就像双向链表中的节点一样。
    这样一来，原本无序的哈希表就拥有了固定的排列顺序。
    
    依靠哈希链表的有序性，我们可以把 Key-Value 按照最后的使用时间进行排序。
"""


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None


class LRUCache:
    """LRU算法模型 --- 哈希链表"""

    def __init__(self, limit):
        self.limit = limit  # 限制哈希表大小
        self.hash = {}
        self.head = None
        self.end = None

    def get(self, key):
        node = self.hash.get(key)
        if node is None:
            return None
        self.refresh_node(node)
        return node.value

    def put(self, key, value):
        node = self.hash.get(key)
        # 如果 key 不存在，插入 key-value
        if node is None:
            if len(self.hash) >= self.limit:
                old_key = self.remove_node(self.head)
                self.hash.pop(old_key)
            node = Node(key, value)
            self.add_node(node)
            self.hash[key] = node
        else:
            # 如果 key 存在，刷新 key-value
            node.value = value
            self.refresh_node(node)

    def remove(self, key):
        node = self.hash.get(key)
        self.remove_node(node)
        self.hash.remove(key)

    def refresh_node(self, node):
        # 如果访问的是尾节点，无须移动节点
        if node == self.end:
            return
        # 移除节点
        self.remove_node(node)
        # 重新插入节点
        self.add_node(node)

    def remove_node(self, node):
        if node == self.head and node == self.end:
            # 移除唯一的节点
            self.head = None
            self.end = None
        elif node == self.end:
            # 移除节点
            self.end = self.end.pre
            self.end.next = None
        elif node == self.head:
            # 移除头结点
            self.head = self.head.next
            self.head.pre = None
        else:
            # 移除中间节点
            node.pre.next = node.pre
            node.next.pre = node.pre
        return node.key

    def add_node(self, node):
        if self.end is not None:
            self.end.next = node
            node.pre = self.end
            node.next = None
        self.end = node
        if self.head is None:
            self.head = node

    def show(self):
        return self.hash


def main():
    lruCache = LRUCache(5)
    lruCache.put("001", "用户 1 信息")
    lruCache.put("002", "用户 2 信息")
    lruCache.put("003", "用户 3 信息")
    lruCache.put("004", "用户 4 信息")
    lruCache.put("005", "用户 5 信息")
    print(lruCache.get("002"))
    print(lruCache.show())
    lruCache.put("004", "用户4信息更新")
    lruCache.put("006", "用户 6 信息")
    print(lruCache.get("001"))
    print(lruCache.get("006"))
    print(lruCache.show())


if __name__ == '__main__':
    main()
